﻿#include <iostream>
#include <queue>

using namespace std;

struct MakeCoffeeData
{
	int start;
	int timeComsume;

	int completedTime()
	{
		return start + timeComsume;
	}

};

struct MakeCoffeeComparator
{

	bool operator()(MakeCoffeeData& a, MakeCoffeeData& b)
	{
		return a.completedTime() > b.completedTime();
	}

};

static int* fastestDrinkCoffeeCompleted(size_t peopleCount, const int* makeCoffeeTime, size_t makeCoffeeCount)
{
	priority_queue<MakeCoffeeData, vector<MakeCoffeeData>, MakeCoffeeComparator> makeCoffeeHeap;
	for (int i = 0; i < makeCoffeeCount; i++)
	{
		MakeCoffeeData data = { 0, makeCoffeeTime[i] };
		makeCoffeeHeap.push(data);
	}

	int* drinkOverTime = (int*)malloc(peopleCount * sizeof(int));
	for (int i = 0; i < peopleCount; i++)
	{
		auto topData = makeCoffeeHeap.top();
		makeCoffeeHeap.pop();
		drinkOverTime[i] = topData.completedTime();
		printf("drinkOverTime[%d]=%d\n", i, drinkOverTime[i]);
		topData.start = topData.completedTime();
		makeCoffeeHeap.push(topData);
	}

	return drinkOverTime;
}

#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)

static int recurWashing(const int* drinkOverTime, size_t peopleCount, const int washedTime, const int volatilizedTime, int index, int washingOverTime)
{
	if (index == peopleCount - 1)
	{
		int byWashing = MAX(drinkOverTime[index], washingOverTime) + washedTime;
		int notByWashing = drinkOverTime[index] + volatilizedTime;
		return MIN(byWashing, notByWashing);
	}

	// 洗，必须等上个杯子洗完才可以使用
	int start = MAX(drinkOverTime[index], washingOverTime);
	// 洗完当前杯子的时间点
	int curEnd = start + washedTime;
	// 洗完后续杯子的时间点
	int subsequentEnd = recurWashing(drinkOverTime, peopleCount, washedTime, volatilizedTime, index + 1, curEnd);
	// 取最慢的才是最终洗完所有杯子的时间点
	int byWashingEnd = MAX(curEnd, subsequentEnd);

	// 自然挥发, 在杯子用完的时候就开始了
	start = drinkOverTime[index];
	curEnd = start + volatilizedTime;
	// 自然挥发是不占用洗碗机的，故调用递归传入的洗完杯子的时间点，还是使用当前传入的!
	subsequentEnd = recurWashing(drinkOverTime, peopleCount, washedTime, volatilizedTime, index + 1, washingOverTime);
	int notByWashingEnd = MAX(curEnd, subsequentEnd);

	return MIN(byWashingEnd, notByWashingEnd);
}

static int washingByStrictTable(const int* drinkOverTime, size_t peopleCount, const int washedTime, const int volatilizedTime)
{
	int washingOverTimeMax = MAX(washedTime, volatilizedTime) * peopleCount;
	int* dp = (int*)malloc((washingOverTimeMax + 1) * peopleCount * sizeof(int));
	// dp[people,time] = dp[time + people * timeMax]
	for (int time = 0; time <= washingOverTimeMax; time++)
	{
		int byWashing = MAX(drinkOverTime[peopleCount - 1], time) + washedTime;
		int notByWashing = drinkOverTime[peopleCount - 1] + volatilizedTime;
		dp[time + (peopleCount - 1) * (washingOverTimeMax + 1)] = MIN(byWashing, notByWashing);
	}

	for (int index = peopleCount - 2; index >= 0; --index)
	{
		for (int washingOverTime = 0; washingOverTime <= washingOverTimeMax; ++washingOverTime)
		{
			// 洗，必须等上个杯子洗完才可以使用
			int start = MAX(drinkOverTime[index], washingOverTime);
			// 洗完当前杯子的时间点
			int curEnd = start + washedTime;
			// 洗完后续杯子的时间点
			int subsequentEnd = dp[curEnd + (washingOverTimeMax + 1) * (index + 1)];
			// 取最慢的才是最终洗完所有杯子的时间点
			int byWashingEnd = MAX(curEnd, subsequentEnd);

			// 自然挥发, 在杯子用完的时候就开始了
			start = drinkOverTime[index];
			curEnd = start + volatilizedTime;
			// 自然挥发是不占用洗碗机的，故调用递归传入的洗完杯子的时间点，还是使用当前传入的!
			subsequentEnd = dp[washingOverTime + (washingOverTimeMax + 1) * (index + 1)];
			int notByWashingEnd = MAX(curEnd, subsequentEnd);

			dp[washingOverTime + (washingOverTimeMax + 1) * index] = MIN(byWashingEnd, notByWashingEnd);
		}
	}

	int res = dp[0];
	free(dp);
	return res;
}

//  有n台咖啡机，用一个数组表示每台咖啡机冲泡一杯咖啡需要多少分钟。比如, [2, 3, 7]，代表有三台咖啡机，
//  第一台咖啡机冲泡一杯咖啡需要2分钟，第二台需要3分钟，第三台需要7分钟。
//  有N个人要喝咖啡，每人只喝一杯咖啡。他们会排队使用这n台咖啡机冲泡咖啡。冲泡咖啡结束，这个人就会立马喝完。
//  有一台洗咖啡杯的机器，洗一个杯子需要a分钟。
//  咖啡杯也可以不洗，喝完咖啡之后，放置b分钟，里面的咖啡会挥发掉，挥发之后杯子也算干净。
//  问：从第一个人冲泡咖啡开始，至少经过多少分钟，所有的咖啡杯都会被洗干净或者挥发干净？
// 
//  思路：
//  这道题目其实有2个问题点：
//  1. 如何高效的利用n台咖啡机，让这N个人以最短的时间喝完咖啡。
//  2. 根据每个咖啡杯用完之后的时间点，如何利用咖啡机和挥发功能，使得咖啡杯干净的总时长最短。
// 
// 问题1：
//  巧妙利用小根堆解决，定义一个结构
// struct CoffeeMachineData {
//	 int start;// 咖啡机开始运作的时间点
//	 int timeConsuming;// 咖啡机冲泡一杯咖啡所花费的时间
//	
//	 // 冲泡一杯咖啡之后的时间点
//   int completedTime() {
//	     return start + timeConsuming;		 
//	 }
// }
// 
// 对于每个咖啡机都声明一个CoffeeMachineData数据，然后根据completedTime()放入小根堆。
//  准备一个长度是N的数组drinkOverTime，用于存放每个人喝完咖啡的时间点.
//  每个人冲泡咖啡的时间点和用哪台机器，取小根堆的堆顶数据top，
//  这个人喝完咖啡的时间点 = top.start + top.timeConsuming，
//  将这个时间点填写到数组drinkOverTime的对应索引位置上，top.start赋值这个人喝完咖啡的时间点,
//  然后再根据top.completedTime()放入到小根堆中...
//  每个人依次做这个操作，直到将drinkOverTime的N个位置都填满。
// 
//  问题2:
// 有了drinkOverTime数据，则利用暴力递归的思路，计算咖啡杯都干净的最小时间点。
//  使用从左往右的尝试思路，第一个杯子，有2种选择，使用洗咖啡杯或自然挥发。
//  第二个杯子，有2种选择，等待洗咖啡杯的机器洗完咖啡杯，然后接着使用咖啡杯洗涤机进行洗杯子，或者自然挥发
//  第三个杯子，有2种选择，等待洗咖啡杯的机器洗完咖啡杯，然后接着使用咖啡杯洗涤机进行洗杯子，或者自然挥发
//  ...
// 
//  有了暴力递归方法，再基于这个方法改出严格表结构方法.
int main_DrinkCoffee()
{
	size_t peopleCount = 10;
	int makeCoffeeTime[] = { 2,3,7 };
	int volatilizedTime = 8;
	int washedTime = 2;
	int makeCoffeeTimeSize = sizeof(makeCoffeeTime) / sizeof(int);
	auto drinkOverTime = fastestDrinkCoffeeCompleted(peopleCount, makeCoffeeTime, makeCoffeeTimeSize);
	auto washingOverTime = recurWashing(drinkOverTime, peopleCount, washedTime, volatilizedTime, 0, 0);
	printf("%d\n", washingOverTime);
	washingOverTime = washingByStrictTable(drinkOverTime, peopleCount, washedTime, volatilizedTime);
	printf("%d\n", washingOverTime);

	free(drinkOverTime);
	return 0;
}